package org.raymond.iworks.study.basic.structure.recursion;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 8皇后问题:
 * 在8x8格的国际象棋上摆放8个皇后,使其不能互相攻击.
 * 即:任意两个皇后都不能处于同一行,同一列或同一斜线上,问有多少种摆法
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 思路分析:
 * 1. 第一个皇后放在第一行第一列
 * 2. 第二个皇后放在第二行第一列,判断是否ok,如果不ok,继续放在第二列,第三列,依次把所有列都放完,找一个ok的.
 * 3. 第三个皇后放在第三行第一列,第二列...直到第八个皇后也能放在一个不冲突的位置上,算是找到一个正确的解.
 * 4. 当得到一个正确解后,在栈回退到上一个栈时,就开始回溯,即将第一个皇后,放到第一列的所有正确解上,全部得到正确的解.
 * 5. 然后回头继续第一个皇后放第二列,后面继续循环1,2,3,4的步骤.
 *
 * 说明:理论上应该创建一个二维数组来表示棋盘,实际上可以通过算法,用一个一维数组即可解决问题.
 * 如arr[8]={0,4,7,5,2,6,1,3}.
 * arr[0]=0,表示第1个皇后放在第1行第1列.
 * arr[1]=4,表示第2个皇后放在第2行第5列.
 * arr[2]=7,表示第3个皇后放在第3行第8列...
 * 数组下标i,表示第i+1行,即第i+1个皇后.数组中的元素j,表示第j+1列.
 */
public class EightQueenProblemTest {
    // 有多少个皇后
    private static int max = 8;
    private static int[] array = new int[max];
    private static List<String> result = new ArrayList<>();

    public static void main(String[] args) {
        long start = System.nanoTime();
        check(0);
        long end = System.nanoTime();
        System.out.printf("count:%d, post:%d", result.size(), (end-start));
    }

    // 放置第n个皇后
    public static void check(int n){
        // n是数组下标,实际应该是n-1,因此放到第n个时,其实已经是max+1个了,
        // 即max已经放好了
        if(n==max){
            print();
            return;
        }
        // 依次放入皇后,并判断是否冲突
        // 这个循环是将皇后放在n行上轮询各个i列进行检查
        for(int i=0; i<max; i++){
            // 先把当前这个皇后n,放到该行的第i列
            array[n]=i;
            // 当放置第n个皇后到i列时,是否冲突
            if(jude(n)){
                // 不冲突,继续放下一个
                check(n+1);
            }
            // 如果冲突,继续执行array[n]=i;循环翻到下一轮,i++
        }
    }

    public static void print(){
        String str = Arrays.toString(array);
        result.add(str);
        System.out.println(str);
    }

    /**
     * 放置第n个皇后时,检查该皇后是否和前面已经摆放的皇后冲突
     * @param n 放置的第n个皇后
     * @return
     * 不需要判断是否同一行,因为皇后必然放在不同的行上.
     */
    public static boolean jude(int n){
        for(int i=0; i<n; i++){
            // array[i]==array[n],是否在同一列
            // Math.abs(n-i)==Math.abs(array[n]-array[i]),是否在同一斜线,
            // 行与列的差值相等,即在同一条斜线上
            // 想象一个棋盘上的两个点之间,行列的差都相等,即斜线相等.
            if(array[i]==array[n]
                    || Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }

    public static int[][] buildMap(){
        // 创建一个二维数组,模拟棋盘
        // 地图, row=8,col=8
        int row = 8;
        int col = 8;
        int[][] map = new int[row][col];
        // 使用1表示墙
        // 上下都置为1,即0行和7行都置为1,逐列设置
        for(int i=0; i<col; i++){
            map[0][i]=1;
            map[row-1][i]=1;
        }
        // 左右都置为1,即0列和6列都置为1,逐行设置
        for(int i=0; i<row; i++){
            map[i][0]=1;
            map[i][col-1]=1;
        }
        // 额外的两堵墙
        map[3][1]=1;
        map[3][2]=1;
        return map;
    }
}
